﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

//class Solution
//{
//    public :
//    string decodeString(string s)
//    {
//        stack<int> nums;
//        stack<string> st;
//        st.push("");
//        int i = 0, n = s.size();
//        while (i < n)
//        {
//            if (s[i] >= '0' && s[i] <= '9')
//            {
//                int tmp = 0;
//                while (s[i] >= '0' && s[i] <= '9')
//                {
//                    tmp = tmp * 10 + (s[i] - '0');
//                    i++;
//                } 
//                nums.push(tmp);
//            } else if (s[i] == '[')
//            {
//                i++; // 把括号后⾯的字符串提取出来
//                string tmp = "";
//                while (s[i] >= 'a' && s[i] <= 'z')
//                {
//                    tmp += s[i];
//                    i++;
//                } 
//                st.push(tmp);
//            } 
//            else if (s[i] == ']')
//            {
//                string tmp = st.top();
//                st.pop();
//                int k = nums.top();
//                nums.pop();
//                while (k--)
//                {
//                    st.top() += tmp;
//                } i
//                    ++; // 跳过这个右括号
//            }
//            else
//            {
//            string tmp;
//            while (i < n && s[i] >= 'a' && s[i] <= 'z')
//            {
//            tmp += s[i];
//            i++;
//            }
//            st.top() += tmp;
//            }
//        }
//        return st.top();
//    }
//};

class Solution {
public:
    string decodeString(string s)
    {
        int n = s.size();

        vector<int> st1;
        vector<string> st2(1, "");
        int i = 0;
        while (i < n)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9')
                {
                    tmp *= 10;
                    tmp += s[i++] - '0';
                }
                st1.push_back(tmp);
            }
            else if (s[i] == '[')
            {
                string tmp;
                i++;
                while (i < n && s[i] >= 'a' && s[i] <= 'z') tmp += s[i++];
                st2.push_back(tmp);
            }
            else if (s[i] == ']')
            {
                string tmp;
                for (int j = 0; j < st1.back(); j++)
                {
                    tmp += st2.back();
                }
                //cout << tmp <<endl;
                st1.pop_back();
                st2.pop_back();
                st2.back() += tmp;
                i++;
            }
            else
            {
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z') tmp += s[i++];
                st2.back() += tmp;
            }
        }

        return st2.back();
    }
};


int main()
{
    string s("3[a10[bc]]");

    Solution sl;
    cout << sl.decodeString(s) << endl;

    return 0;
}




//字符串相乘
class Solution {
public:
    string multiply(string num1, string num2)
    {
        if (num1[0] == '0' || num2[0] == '0') return "0";
        int n = num1.size();
        int m = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        int size = n + m - 1;
        int tmp[size];
        for (int i = 0; i < size; i++) tmp[i] = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int x = num1[j] - '0';
                int y = num2[i] - '0';
                tmp[i + j] += x * y;
            }
        }

        string ans;
        int carry = 0;
        for (int i = 0; i < size; i++)
        {
            carry += tmp[i];
            ans += (carry % 10) + '0';
            carry /= 10;
        }
        if (carry) ans += carry + '0';
        reverse(ans.begin(), ans.end());
        return ans;
    }
};



//删除字符串中的所有相邻重复项
class Solution {
public:
    string removeDuplicates(string s)
    {
        string ans = "";
        for (auto c : s)
        {
            if (ans == "" || ans.back() != c)
            {
                ans += c;
            }
            else
            {
                ans.pop_back();
            }
        }

        return ans;
    }
};

//比较含退格的字符串
class Solution {
public:
    bool backspaceCompare(string s, string t)
    {
        string tmp1;
        string tmp2;
        for (auto c : s)
        {
            if (tmp1.size() && c == '#') tmp1.pop_back();
            else if (c != '#') tmp1 += c;
        }

        for (auto c : t)
        {
            if (tmp2.size() && c == '#') tmp2.pop_back();
            else if (c != '#') tmp2 += c;
        }

        return tmp1 == tmp2;
    }
};


//基本计算器 II
class Solution {
public:
    int calculate(string s)
    {
        stack<int> st;
        char signal = '+';
        int size = s.size();
        for (int i = 0; i < size;)
        {
            if (s[i] == ' ') i++;
            else if (s[i] < '0' || s[i] > '9')
            {
                signal = s[i];
                i++;
            }
            else
            {
                int tmp = 0;
                while (i < size && s[i] >= '0' && s[i] <= '9')
                {
                    tmp *= 10;
                    tmp += s[i] - '0';
                    i++;
                }
                if (signal == '+') st.push(tmp);
                else if (signal == '-') st.push(-tmp);
                else
                {
                    int ret = st.top();
                    st.pop();
                    if (signal == '*') ret *= tmp;
                    else ret /= tmp;
                    st.push(ret);
                }
            }
        }
        int ans = 0;
        while (!st.empty())
        {
            ans += st.top();
            st.pop();
        }

        return ans;
    }
};

//字符串解码
class Solution {
public:
    string decodeString(string s)
    {
        int n = s.size();

        vector<int> st1;
        vector<string> st2(1, "");
        int i = 0;
        while (i < n)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (s[i] >= '0' && s[i] <= '9')
                {
                    tmp *= 10;
                    tmp += s[i++] - '0';
                }
                st1.push_back(tmp);
            }
            else if (s[i] == '[')
            {
                string tmp;
                i++;
                while (i < n && s[i] >= 'a' && s[i] <= 'z') tmp += s[i++];
                st2.push_back(tmp);
            }
            else if (s[i] == ']')
            {
                string tmp;
                for (int j = 0; j < st1.back(); j++)
                {
                    tmp += st2.back();
                }
                //cout << tmp <<endl;
                st1.pop_back();
                st2.pop_back();
                st2.back() += tmp;
                i++;
            }
            else
            {
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z') tmp += s[i++];
                st2.back() += tmp;
            }
        }

        return st2.back();
    }
};

//验证栈序列
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
    {
        stack<int> st;
        int i = 0;
        int n = popped.size();
        for (auto e : pushed)
        {
            st.push(e);
            while (!st.empty() && i < n && st.top() == popped[i])
            {
                st.pop();
                i++;
            }
        }

        return st.empty();
    }
};





